#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;
class Solution {
public:
    int findMin(vector<vector<int> >& mp) {
        if(mp.size()==0||mp[0].size()==0){
            return 0;
        }
        int r=mp.size(),c=mp[0].size();
        auto v=vector<vector<int> >(r,vector<int>(c,0));
        v[0][0]=mp[0][0];
        for(int i=1;i<r;i++){
            v[i][0]=v[i-1][0]+mp[i][0];
        }
        for(int j=1;j<c;j++){
            v[0][j]=v[0][j-1]+mp[0][j];
        }
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                v[i][j]=min(v[i-1][j],v[i][j-1])+mp[i][j];
            }
        }
        return v[r-1][c-1];
    }
};

int main(){
    vector<vector<int> > v={{1,3,1},{1,5,1},{4,2,1}};
    Solution s;
    cout << s.findMin(v)<<endl;


    return 0;
}